﻿ 

namespace Common.Algorithm.Core;

public class SimpleGeneticTSPService
{
    private int[] path { get; set; }
    public List<int> bestPath = new List<int>();

    private static Random randomBuilder = new Random();
    private static MatrixBuilder<double> matBuilder { get; set; } = Matrix<double>.Build;

    public int crossoverNum { get; set; }
    public int mutationNum { get; set; }
    public int populationNum { get; set; } = 500;
     
    private static Matrix<double> matrixDistance;

    public SimpleGeneticTSPService(IEnumerable<GraphEdge> edges)
    {
        var groups = edges.GroupBy(e => e.stVertexId);
        var cityNum = groups.Count();
        matrixDistance = matBuilder.Dense(cityNum, cityNum);

        for (int i = 0; i < cityNum; i++)
        {
            for (int j = 0; j < cityNum; j++)
            {
                matrixDistance[i, j] = i == j ? 0 : edges.At(i, j).weight;
            }
        }

        path = new int[cityNum];
        for (int i = 0; i < cityNum; i++)
        {
            path[i] = i;
        }
        bestPath = path.ToList();

        crossoverNum = cityNum / 2;
        mutationNum = cityNum / 10;
    }

    public SimpleGeneticTSPService(Matrix<double> _matrixDistance)
    {
        matrixDistance = _matrixDistance;
        int cityNum = _matrixDistance.RowCount;

        path = new int[cityNum];
        for (int i = 0; i < cityNum; i++)
        {
            path[i] = i;
        }
        bestPath = path.ToList();

        crossoverNum = cityNum / 2;
        mutationNum = cityNum / 10;
    }

    public void RunAlgm(int numberOfGeneration)
    {
        List<int[]> population = new List<int[]>();
        for (int i = 0; i < populationNum; i++)
        {
            population.Add(path.OrderBy(p => randomBuilder.Next(path.Count())).ToArray());
        }

        while (numberOfGeneration > 0)
        {
            numberOfGeneration--;

            List<int[]> childs = new List<int[]>();
            for (int i = 0; i < crossoverNum; i++)
            {
                var father = population[randomBuilder.Next(population.Count)];
                var mother = population[randomBuilder.Next(population.Count)];
                var child = Crossover(father, mother, father.Count() / 2);
                if (child.Length != path.Length) continue;//染色体数量变化  定义为其他物种 不计入种群
                childs.Add(child);
            }

            List<int[]> mutates = new List<int[]>();
            for (int i = 0; i < mutationNum; i++)
            {
                var mutate = population[randomBuilder.Next(population.Count)];
                mutate = Mutation(mutate);
                if (mutate.Length != path.Length) continue;//染色体数量变化  定义为其他物种 不计入种群
                mutates.Add(mutate);
            }

            population = population.Concat(childs).Concat(mutates)
                .OrderBy(p => PathLength(p))
                .ToList();

            population = population.GetRange(0, populationNum);

            //bool hasSame =   population.Any(p => p.GroupBy(v => v).Any(g => g.Count() > 1));
            // p.GroupBy(v => v).Any(g => g.Count() > 1)

        }

        bestPath = population.First().ToList();
    }


    /// <summary>
    /// 计算当前路径的总路程
    /// </summary>
    /// <param name="_paths"></param>
    /// <returns></returns>
    public static double PathLength(int[] _paths)
    {
        double pathSum = 0;
        for (int i = 0; i < _paths.Length - 1; i++)
        {
            pathSum += matrixDistance[_paths[i], _paths[i + 1]];
        }
        pathSum += matrixDistance[_paths.Last(), _paths.First()];
        return pathSum;
    }

    /// <summary>
    /// 染色体互换
    /// </summary>
    /// <param name="_pathSt"></param>
    /// <param name="_pathEd"></param>
    /// <param name="_num"></param>
    /// <returns></returns>
    public static int[] Crossover(int[] _pathSt, int[] _pathEd, int _num)
    {
        List<int> pathSt = _pathSt.ToList();
        List<int> pathEd = _pathEd.ToList();

        List<int> childChromosome = new List<int>();

        int num = _num;

        List<int> removeIndexs = new List<int>();
        for (int i = 0; i < num; i++)
        {
            removeIndexs.Add(randomBuilder.Next(pathEd.Count - 1));
        }

        List<int> removeValues = new List<int>();
        removeIndexs.ForEach(i => removeValues.Add(pathEd[i]));
        removeValues.ForEach(v => pathEd.Remove(v));
        var stSegment = pathSt.Where(p => removeValues.Contains(p)).ToList();

        childChromosome = pathEd.Concat(stSegment).ToList();

        return childChromosome.ToArray();
    }


    /// <summary>
    /// 随机长度编译
    /// </summary>
    /// <param name="_path"></param>
    /// <returns></returns>
    public static int[] Mutation(int[] _path)
    {
        var sourceChromosome = _path.ToList();
        var targetChromosome = _path.ToList();

        int index1 = randomBuilder.Next(sourceChromosome.Count);
        int index2 = randomBuilder.Next(sourceChromosome.Count);

        var minIndex = Math.Min(index1, index2);
        var maxIndex = Math.Max(index1, index2);
        if (minIndex == maxIndex) return sourceChromosome.ToArray();

        var mutationSt = sourceChromosome.GetRange(0, minIndex);
        var mutationSegment = sourceChromosome.GetRange(minIndex, maxIndex - minIndex);
        var mutationEd = sourceChromosome.GetRange(maxIndex, sourceChromosome.Count() - maxIndex);
        
        mutationSegment = mutationSegment.OrderBy(s => randomBuilder.Next()).ToList();

        targetChromosome = mutationSt.Concat(mutationSegment).Concat(mutationEd).ToList();
        //var EEE=    targetChromosome.GroupBy(v => v).Where(g => g.Count() > 1).Select(g=>g.First()).ToList();
        return targetChromosome.ToArray();
    }

    /// <summary>
    /// 指定编译片段长度
    /// </summary>
    /// <param name="_path"></param>
    /// <param name="_num"></param>
    /// <returns></returns>
    public static int[] Mutation(int[] _path, int _num)
    {
        var sourceChromosome = _path.ToList();
        int num = _num;

        var targetChromosome = _path.ToList();
        //防止完全超变异发生
        if (num > sourceChromosome.Count())
        {
            num = Int32.Parse((num / 2).ToString());
        }

        var minIndex = randomBuilder.Next(sourceChromosome.Count - num - 1);
        var maxIndex = minIndex + num;

        var mutationSt = sourceChromosome.GetRange(0, minIndex);
        var mutationSegment = sourceChromosome.GetRange(minIndex, maxIndex - minIndex);
        var mutationEd = sourceChromosome.GetRange(maxIndex, sourceChromosome.Count() - maxIndex);

        mutationSegment = mutationSegment.OrderBy(s => randomBuilder.Next()).ToList();

        targetChromosome = mutationSt.Concat(mutationSegment).Concat(mutationEd).ToList();

        return targetChromosome.ToArray();

    }

}
